The invention relates generally to mathematical algorithms for data transmissions, and, more particularly, to algorithms for performing modulus conversions of transmitted data.
Conventional computer systems transmit data using modems connected to telephone lines or other communication media. Generally, there are two types of modem in such a system, server modems and client modems. Signal directions are generally referred to in this area as downstream, from server modems to client modems, and upstream, from client modems to server modems. Server modems are generally used by Internet service providers (ISPs) for transmitting signals downstream to and receiving signals upstream from client modems. Similarly, client modems are generally used by customers of ISPs, and are configured to send signals upstream to and receive signals downstream from ISP server modems.
Each type of modem typically uses an analog to digital converter and a digital to analog converter, (A/D-D/A converter) typically combined into a single device called a CODEC. This CODEC converts incoming analog signals to digital signals that can be processed by a signal-processing unit and converts digital signals from a signal processing unit to outgoing analog signals that can be transmitted on a communication medium such as a telephone line. In many cases, server modems do not have their own CODECs, but rely on the CODECs within the telephone network to do the conversions. The signal processing unit, sometimes referred to as a xe2x80x9cdata pump,xe2x80x9d is conventionally a dedicated chip known as a Digital Signal Processor (DSP), which is preprogrammed with algorithms for converting the digital signals into information bits and vice versa.
The modem may also include a second dedicated chip, sometimes called the xe2x80x9ccontroller,xe2x80x9d which is a microcontroller preprogrammed to control the DSP, convert the information bits from the DSP into data usable by the computer system, and convert data from the computer system into information bits for the DSP. The controller may implement certain schemes to correct errors in the information bits, and may also implement certain schemes to compress the information bits for more efficient transmission. Some modems eliminate the dedicated controller chip by performing the control functions on the host computer system. These modems are commonly referred to as controllerless modems. Other modems may perform some or all of the signal processing functions on the host computer system using techniques commonly referred to as Host Signal Processing (HSP.)
Modem modulation schemes used in modem communication systems are typically defined in terms of analog signals. Many modulation schemes operate by altering the characteristics of a sine wave, the frequency of which is referred to as the carrier frequency. For example, Quadrature Amplitude Modulation (QAM) operates by altering the amplitude and phase of a carrier frequency at a fixed rate. Other modulation schemes operate without a carrier. For example, Pulse Coded Modulation (PCM) operates by directly altering the level of a signal at a fixed rate. In either case, this fixed rate is known as the baud frequency or symbol frequency. Since most modern modems use digital signal processing techniques, these analog signals must be converted to digital form using a sampling rate, which is often a multiple of the baud frequency. Thus, an integer number of samples can be thought of as representing a xe2x80x9cbaudxe2x80x9d or xe2x80x9csymbol.xe2x80x9d Depending on the modulation scheme and the sophistication of the algorithms it uses, the symbols, either individually or in groups, represent a certain number of information bits. The relationship between the information bits and the transmitted symbols is determined by a mapping scheme. The average number of information bits transmitted per second is commonly called the xe2x80x9cdata ratexe2x80x9d or xe2x80x9cbit rate.xe2x80x9d
Standard protocols for modem modulation schemes have been developed to improve compatibility in the telecommunications industry. The International Telecommunications Union (ITU), formerly the International Telegraph and Telephone Consultative Committee (CCITT), for example, has developed standard recommendations that evolve with the changing technology in the modem industry. Earlier recommendations such as V.21, V.22 and V.23 use frequency division multiplexing (FDM) for duplex communication. Newer recommendations such as V.32bis, V.34, V.90 and V.92 use echo cancellation for duplex communication. V.90 and V.92 describe duplex communication using PCM modulation in at least one direction. Modems designed according to V.90 or V.92 are sometimes called 56 kbps modems, referring to the maximum bit rate specified in the downstream direction. All modems implementing a particular recommendation must use specified modulation and mapping schemes when transmitting data across the data transmission system, in order to ensure interoperability among multiple vendors"" products.
Modulation schemes typically define sets of allowable symbol parameters known as constellations. Mapping methods provide ways to represent information bits to be transmitted in terms of available points in the constellations. In both the V.90 and V.92 recommendations, multiple modulus conversion (MMC) is employed as a mapping scheme in order to map long frames of information bits onto multiple constellations of different sizes. In particular, the V.90 recommendation specifies MMC to be used in the downstream direction, from the server modem to the client modem. The V.92 recommendation specifies MMC to be used in both directions.
In conventional applications of MMC, input data is used to form a quotient, which is successively divided by a set of known moduli. The remainders of each division are used as the output of the process. This process is a great burden on a modem processor, because typically division operations require multiple cycles to perform. Also, typically the input data is larger than the modem processor can handle with one operation. To address these problems, several techniques have been developed to perform such calculations. One commonly used method uses a long division algorithm, whereby the incoming quotient is partitioned into several segments, each requiring a separate division operation.
In general, the MMC algorithm takes as input a number Q0, a non-negative integer. In addition, the algorithm takes as input a plurality of moduli Yi, where 1xe2x89xa6ixe2x89xa6M, which are all positive integers. Typically, Yixe2x89xa72 and Q0 less than Y1*Y2* . . . YM. The output of the algorithm is a set of values Qi and Ri, all non-negative integers, such that the following mathematical relationships hold:
Q0=Y1*Q1+R1
Q1=Y2*Q2+R2
. . .
Qixe2x88x921=Yi*Qi+Ri
where
0xe2x89xa6Ri less than Yi
Equivalently, Q0 can be expressed in terms of the remainders produced by the MMC process and the respective moduli, Yi:
Q0=R1+R2Y1+R3Y1Y2+. . . +RMY1Y2 . . . YMxe2x88x921+QMY1Y2. . . YM
Note that if Q0 less than Y1*Y2* . . . YM, as is typically the case in a communication system, then QM=0.
This algorithm requires that a division operation be done for each modulus, resulting in an output quotient and remainder for each modulus. The division corresponding to the final modulus YM may be skipped if the input is limited as described above, so that QM is known in advance to be 0. In that case, it can be shown that RM=QMxe2x88x921.
The following example illustrates the mathematical concept of MMC. All values are expressed in decimal format. In this example, the input Q0=933, and there are four input moduli: Y1=5, Y2=6, Y3=7, and Y4=8. Here are the steps in the process:
1. Receive the input value of 933.
2. Divide the input by first modulus, 5. 933/5=quotient 186, remainder 3.
3. Divide new quotient by second modulus, 6. 186/6=quotient 31, remainder 0.
4. Divide new quotient by third modulus, 7. 31/7=quotient 4, remainder 3.
5. Divide new quotient by fourth modulus, 8. 4/8=quotient 0, remainder 4.
In an MMC process, the final outputs are 3, 0, 3 and 4 respectively. Note that the final division could have been skipped, since Q0 less than Y1Y2Y3Y4 (933 less than 1680) and therefore Q4=0. The final remainder, R4, is equal to the next-to-last quotient, Q3.
In a conventional implementation of MMC, there are several system constraints. Typically, a device implementing MMC operates on values, in the binary, or Base 2, number system. However, MMC calculations can be implemented in any Base B number system. For example, the decimal number system (B=10) could be used. Typically, the device is constrained to perform arithmetic operations on values with a limited number of digits in the Base B numbering system. Since Q0 may typically be represented with more digits than the device can handle in one calculation, xe2x80x9clong divisionxe2x80x9d methods are typically used to calculate the division result.
Long division is an iterative technique well known in mathematics. In A course of mathematics, by Charles Hutton, published in 1816, this type of division is described as follows: xe2x80x9c. . . the dividend is resolved into parts, and by trial is found how often the divisor is contained in each of those parts, one after another, arranging the several figures of the quotient one after another, into one number.xe2x80x9d (pp. 18-19.) These days, long division is generally taught in elementary school as a pencil-and-paper method for doing division of large numbers (i.e., numbers that are difficult to divide in one""s head.)
Long division is also well known in the art of computer science as a method for computing divisions of xe2x80x9clargexe2x80x9d numbers, defined as numbers with precision greater than can be accommodated in single registers or single calculations on the target computer. For example, in The Art of Computer Programming, 2nd ed., by Donald Knuth, published in 1981, a computer algorithm is presented to solve the general problem of long division. (pp. 255-260.) As in the pencil-and-paper method, computer long division requires partitioning one or more large numbers into a series of smaller numbers. Knuth""s algorithm allows for these smaller numbers to be in any arbitrary base, so they could be the digits of a Base 10 number (as in the pencil-and-paper method taught by Hutton) or they could be in a Base that is a power of two, which is more likely since computers are typically designed for binary arithmetic. For example, the smaller numbers could be 4-bit short words (equivalently, digits in Base 16.)
MMC could be implemented using Knuth""s long division algorithm directly. However, some simplifications can be made due to the nature of MMC. For example, Knuth""s algorithm allows both the divisor and dividend to be large numbers, which are partitioned into smaller numbers. However, in MMC, the divisors are typically small enough to be handled by the computer directly, so only the dividends need to be partitioned. Also, in Knuth""s algorithm the intermediate quotients are estimates that may have some error. Therefore, the intermediate remainders need to be tested to make sure they fall in the valid range. In a MMC application, the divisors and the partitions of the dividends can be constrained so that this test can be eliminated. One example of a MMC method using a simplified long division algorithm can be found in U.S. Pat. No. 6,065,030, Method and Apparatus for Implementing Short-Word Division Techniques in a Multiple Modulus Conversion Context, disclosed by Xuming Zhang.
To implement MMC using Zhang""s technique, Q0 is first partitioned into k+1 segments as follows:
Q0=Q0,0+Q0,1*Bn(0)+Q0,2*Bn(0)+n(1)+. . . Q0,k*Bn(0)+n(1)+. . . +n(kxe2x88x921)
where n(j) is the number of digits in the base B numbering system used to represent Q0,j.
The division of Q0 by the first modulus Y1 can be done by successively dividing each Q0,j by Y1, as represented in the following pseudo-code:
R1,k+1=0
For (j=k;jxe2x89xa70;jxe2x80x94)
{Q1,j=floor((Q0,j+R1,j+1*Bn(j))/Y1) R1,j=Q0,jxe2x88x92Q1,j*Y1}
The floor( ) function is defined as the greatest integer less than or equal to its argument. The result of this division is a quotient and a remainder, as follows:
Q1=Q1,0+Q1,1*Bn(0)+Q1,2*Bn(0)+n(1)+. . . Q1,k*Bn(0)+n(1) +. . . +n(k)xe2x88x921)
R1=R1,0
The remaining moduli Yi can be divided in a similar fashion:
Ri,k+1=0
For (j=k;jxe2x89xa70; jxe2x80x94)
{Qi,j=floor((Qixe2x88x921,j+Ri,j+1*Bn(j))/Yi)
Ri,j=Qixe2x88x921,jxe2x88x92Qi,j*Y1}
The final quotients and remainders are then expressed as:
Qi=Qi,0+Qi,1*Bn(0)+Qi,2*Bn(0)+n(1)+. . . Qi,k*Bn(0)+n(1) +. . . +n(kxe2x88x921 )
Ri=Ri,0
Zhang also suggests that the long division loop (or, as he calls it xe2x80x9cshort word divisionxe2x80x9d) can be skipped whenever the quotient is small enough to be handled in a single conventional division operation.
Returning to the previous example where Q0=933, Y1=5, Y2=6, Y3=7, and Y4=8, assume the following constraint exists: for conventional division operations, the quotient is limited to 2 digits and the divisor is limited to 1 digit. The steps of Zhang""s MMC process, constrained according to the above assumption, are as follows. First, Q0, 933, is expressed as (9*100)+(3*10)+3. Then, long division is used to divide the input by a first modulus, 5.
a. Dividing 9 by 5, gives a quotient of 1, and remainder of 4.
b. next, 4*10 is added to 3, giving 43
c. Dividing 43 by 5, gives a quotient of 8, remainder 3
d. next, 3*10 is added to 3, giving 33
e. Dividing 33 by 5, gives a quotient 6, remainder 3
f. The new quotient is then formed from the quotients, (1*100)+(8*10)+6=186
g. The final remainder is 3.
This is the true quotient and remainder of 933/5, which is 186, remainder 3.
Next, long division is used to divide new quotient by a second modulus, 6, the quotient, 186, is expressed as (1*100)+(8*10)+(6*1).
a. First, 1 is divided by 6, giving a quotient of 0, remainder 1.
b. Next, 1*10 is added to 8, giving 18.
c. Dividing 18 by 6, gives a quotient of 3, remainder 0.
d. Next, 0*10 is added to 6, giving 6.
e. Dividing 6 by 6, gives a quotient of 1, remainder 0.
f. The new quotient is formed, (0*100)+(3*10)+1=31
g. The final remainder is 0.
This is the true quotient and remainder of 186/6, which is 31, remainder 0.
Since last quotient of 31 has only 2 digits, conventional division can be used to divide the quotient by a third modulus, 7. Dividing 31 by 7, gives a quotient of 4, remainder 3.
Similarly, since the last quotient of 4 has only 1 digit, conventional division can be used to divide it by fourth modulus, 8. Dividing the quotient 4 by 8, gives a final calculated quotient of 0, remainder 4.
In this conventional method, the process checks the new quotient before doing the long division procedure. If the resultant quotient is less than a threshold, it does a conventional divide. This saves some divide instructions for the later divisions. The check, however, adds yet more processing cycles to the process.
The final remainders, which are the outputs of the MMC, are 3, 0, 3 and 4 respectively. So, Zhang""s method results in the correct answer for this example.
Referring to the MMC parameters as specified in both V.90 and V.92 recommendations, M, the total number of moduli, also represents the number of symbols that are transmitted in a single data frame. For the downstream transmitter in V.90 and V.92, M=6. For the PCM upstream transmitter in V.92, M=12. For the downstream transmitter in V.90 and V.92, the values of Yi represent the number of signal point magnitudes contained in the signal point constellation that is associated with the ith phase of the data frame. For the PCM upstream transmitter in V.92, the values of Yi represent the number of equivalence classes associated with the ith phase of the data frame. Each equivalence class has one or more associated signal point magnitudes in the signal point constellation.
The problem with using the long division method in conventional systems, such as a 56 kbps based modem system, is that it requires a large number of divide operations to get to the final result. Performing binary division is typically extremely inefficient, depending on the processor used in the system. According to the V.92 recommendation in particular, MMC operations are required on the transmission operations of both server modems and client modems. Thus, now all devices that transmit data must be capable of performing MMC encoder operations to be compliant with the V.92 recommendation. The complexity of performing many division operations greatly burdens the system processors. For example, in an Intel(trademark) Pentium(trademark) processor, a 32-bit integer divide requires 46 cycles by the processor to perform the operation. A floating-point divide requires 39 cycles by the Pentium(trademark) processor to perform the operation. This is in sharp contrast to other mathematical operations that can be performed on data bits in such processors.
Therefore, there exists a need in the art of modem system design to develop devices and methods for more efficiently performing multiple modulus conversion calculations. As will be seen, the invention accomplishes this in an elegant manner.
A method and device are provided for use in a communication system having means configured to map frames of information bits onto predetermined communication signal parameters that allow computation of multiple modulus conversion (MMC) outputs using little or no division operations. The invention enables the representation of an input as a plurality of sub-quotients, the performing of a multiplication operation to multiply at least one of the sub-quotients by a multiplicand and the determining of an index value associated with the multiplicand, the index value being responsive to the inverse modulus multiplication operation. Unlike conventional methods, instead of using burdensome division operations, multiplication and logical shift operations are used to produce pseudo-quotients and pseudo-remainders, which may be corrected in a final step to produce correct MMC outputs. This allows for more efficient implementation, since division is typically less efficient than multiplication and logical shift. The method and device operate on MMC inputs that may be partitioned into sub-quotients of varying numbers of digits in any numbering system.